The information technology revolution has changed modern life. We create a torrent of data for ourselves, for our organizations, and for the planet. Despite the proliferation of new kinds of storage media and the precipitous drop in storage cost, there never seems to be enough storage. But our data must be stored. This presents a problem.
Meanwhile, people and organizations are increasingly connected. Despite the huge investments in communication infrastructure of all sorts, both wired and wireless, there never seems to be enough bandwidth. Paradoxically, storage and bandwidth are surprisingly ubiquitous and irritatingly scarce at the same time. This presents a problem.
The desire for people and organizations to store more data and to communicate more content has never been greater. Our want can never be quenched. When advances in video recording let us store hundreds of hours of broadcast quality video on an unobtrusive box on a bookshelf, along comes high-definition video to make our demands ever greater. This presents a problem.
Data compression is one of technology's cures. It makes modest storage appear majestic. It makes miniscule bandwidth appear mighty. Pocket-size gadgets hold hours of home movies. Tenuous cell phone connections carry live video feeds. While storage and bandwidth remain maddeningly finite, compression helps meet our demands.
A compression algorithm embeds a model of the original data from which it is able to recreate the original (or a close representation) from a stream of fewer bits.
The LZW (Lempel-Ziv-Welch) family of algorithms has been successfully employed for lossless compression of character streams. The LZW compression scheme is able to adapt to the statistical properties of the character stream itself. However, LZW requires that the string and character components of a code be communicated to a decoder before it can be used. This may present a problem.
For image compression, the JPEG standard has proven to be highly successful. For video compression, the MPEG family of standards finds wide acceptance. However, both JPEG and MPEG use fixed transforms which lack the ability to adapt to the input stream. This may present a problem.
Researchers have explored the possibility of compressing images using transforms that adapt to the data, but the need to send information about the transform itself, referred to as “side information,” tends to negate gains that the adaptive transforms provide. This presents a problem.